import java.util.*;

/**
 * @program: LeetCode
 * @description: LeetCode :
 * @author: WXY
 * @create: 2022-12-27 10:44
 * @Version 1.0
 **/

public class offer_ten1_RandomizedSet {
   static class RandomizedSet {
        Map<Integer,Integer> map;
        List<Integer> list;
        int size;
        static Random random = new Random();

        /** Initialize your data structure here. */
        public RandomizedSet() {
            map = new HashMap<>();
            list = new ArrayList<>();
        }

        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if (map.containsKey(val))return false;
            list.add(val);
            map.put(val,size++);
            return true;
        }

        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val))return false;
            int index = map.get(val);
            int lastNum = list.get(--size);
            list.set(index, lastNum);
            map.put(lastNum, index);
            map.remove(val);
            list.remove(size);
            return true;
        }

        /** Get a random element from the set. */
        public int getRandom() {
            return list.get(random.nextInt(size));
        }
    }

}
